iT邦幫忙

2024 iThome 鐵人賽

DAY 20
1

引言

演算法中,遞迴通常是用來處理分治問題的利器,像是快速排序 (QuickSort) 就是其中的典型範例。然而,傳統遞迴有一個問題——當數據集非常龐大時,會因為堆疊過深而導致記憶體溢出。為了解決這個問題,我們可以用迭代來取代遞迴,並通過手動管理堆疊來實現遞迴效果。這樣的解法雖然複雜,但為開發者提供了更高的可控性,並避免了記憶體過載的風險。

在本文中,我們探討了三種不同的快速排序視覺化實現方式,從經典的遞迴到手動管理堆疊,再到使用生成器的優雅解法。這些實現方式各有優缺點,讓我們能更靈活地選擇適合不同場景的解決方案!

快速排序

https://ithelp.ithome.com.tw/upload/images/20241003/20135197yRXsunQMS4.png

線上查看動畫效果

這個快速排序的範本是基於遞迴的經典版。它將最後一個元素選作樞軸 (pivot),並將陣列分為兩部分:較小的元素放在左邊,較大的元素放在右邊。然後對兩部分遞迴進行相同的操作。

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    const pivot = arr[arr.length - 1];
    const left = [];
    const right = [];
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] < pivot) left.push(arr[i]);
        else right.push(arr[i]);
    }
    return [...quickSort(left), pivot, ...quickSort(right)];
}

這種實現的優點是易於理解和編寫,直接使用遞迴的方式解決問題。但缺點在於它需要額外的空間來存儲每次遞迴的左右陣列,而且較難植入視覺化的程式碼。

迭代方程式

這一版本使用一個模擬遞迴的方式,通過 stack 來保存要處理的子陣列範圍,避免了遞迴調用,對記憶體非常友善。並且不同於範例的版本,我們會透過 pivot 來找到左界和右界,並進行交換,以下是程式的結構,每次執行位於 stack 陣列最上層的排序,接著透過手動管理不同的步驟,決定 pop 和 push 的時機。

class SortAlgorithm{
    quickSortSetting(columns){
        this.stack = [{'left': 0, 'right': columns.length - 1}];
        this.partitionPhase = "0.SetPivot";
        this.pivot = columns.length - 1;
        this.j = 0;
    }
    quickSort(columns){
        const len = this.stack.length;
        const {left, right} = this.stack[len - 1];
        const pivot = this.pivot;
        const frame = 60;
        switch(this.partitionPhase){
            case "0.SetPivot":
            case "1.FindLeftBound":
            case "2.FindRightBound":
            case "3.SwapBoth":
            case "4.EndPartition":
            default:
        }
    }
}
  • stack 儲存尚未排序的子陣列範圍,初始狀態要求對整個數列進行排序,因此初始值是 {left: 0, right: columns.length - 1}
  • partitionPhase 用來管理分區過程的狀態,從 "0.SetPivot" 開始。
  • pivot 初始設置為最後一個元素的位置。
  • j 用來記錄當前步驟的迭代次數。

階段0:設置 Pivot

這一步從中間位置選出 pivot,並將其移動到右端。這是為了方便後續的分區操作,且中間值通常能夠提供較好的分區效果。

case "0.SetPivot":
    const a = columns[Math.floor((left + right) / 2)];
    const b = columns[right];
    SortAlgorithm.swapColumn(a, b, frame);
    this.leftBound = left;
    this.rightBound = right - 1;
    this.pivot = right;
    this.partitionPhase = "1.FindLeftBound";
    this.j = 0;
    break;

階段1:尋找左界

接著程式會從左側開始搜尋,找出一個大於等於 pivot 的元素,這個元素將作為左界 (leftBound)。

case "1.FindLeftBound":
    if(columns[this.leftBound + this.j].height >= columns[pivot].height){
        this.leftBound = this.leftBound + this.j;
        this.partitionPhase = "2.FindRightBound";
        this.j = 0;
        break;
    }
    this.j++;
    break;

階段2:尋找右界

在這一步,程式從右側往回搜尋,尋找一個小於等於 pivot 的元素,作為右界 (rightBound)。

case "2.FindRightBound":
    if(columns[pivot].height >= columns[this.rightBound - this.j].height || this.rightBound - this.j <= this.leftBound){
        this.rightBound = this.rightBound - this.j;
        this.partitionPhase = "3.SwapBoth";
        break;
    }
    this.j++;
    break;

階段3:交換兩端元素

此時會有兩個分支,如果左右界仍位於左右兩側,將兩者交換後,會回到第一步重新尋找新的左右界;反之,當左右界交錯,表示已經分區完畢,此時將樞軸和左界交換(樞軸一開始被擺放在最右邊),並結束分區。

case "3.SwapBoth":
    if(this.leftBound < this.rightBound){
        const a = columns[this.leftBound];
        const b = columns[this.rightBound];
        SortAlgorithm.swapColumn(a, b, frame);
        this.partitionPhase = "1.FindLeftBound"
        this.j = 0;
        this.leftBound++;
        this.rightBound--;
    }
    else{
        const a = columns[this.leftBound];
        const b = columns[pivot];
        SortAlgorithm.swapColumn(a, b, frame);
        this.partitionPhase = "4.EndPartition";
        this.pivot = this.leftBound;
    }
    break;

階段4:完成分區

當分區完成後,我們便能根據新的 pivot 將陣列分成左右兩個子陣列,並用物件的形式將其索引範圍推入 stack,繼續進行下一輪的分區。當 stack 為空時,排序過程結束。

case "4.EndPartition":
    this.stack.pop();
    if(left < pivot - 1) this.stack.push({'left': left, 'right': pivot - 1});
    if(pivot + 1 < right) this.stack.push({'left': pivot + 1, 'right': right});
    if(this.stack.length == 0) return true;
    this.partitionPhase = "0.SetPivot";
    break;

這麼做,除了模擬了遞迴,利用棧來記錄子區間。每個子區間在分割後不會創建新的陣列,優化了空間使用。還能把分區過程被分解為幾個步驟,並且允許在每步中進行動畫展示。

迭代器和生成器

這段程式碼介紹了一個簡潔的快速排序解法,使用了 迭代生成器 (Generator Function) 來模擬遞迴過程。與前一版本不同的是,它利用 yield 和 yield* 來達成流程的中斷與繼續,這樣不但能保持程式結構簡潔,同時也便於動畫展示和異步操作。

延續前幾次的做法,回傳值 (true, false) 表示動畫是否結束,由此可以看見我們將停止條件設定在最後一行。並且注意到,遞迴本質上是在函式內呼叫一個新的函式,如果該函式是一個生成器,我們要用 yield* 來呼叫,才能正確使用:

class SortAlgorithmIterable{
    * quickSortMaker(columns, left = 0, right = columns.length - 1) {
        yield false;
        if (left >= right) return;
        const pivotIndex = yield* SortAlgorithm.partition(columns, left, right);
        yield* this.quickSortMaker(columns, left, pivotIndex - 1);
        yield* this.quickSortMaker(columns, pivotIndex + 1, right);
        if(left == 0 && right == columns.length - 1) yield true;
    }
}

在分區的階段,我們採用另一種方法,一次性歷便整個陣列,將值小於 pivot 的都往左側集中,並記錄左側的長度,最後,再把 pivot 移動到左側的末尾,以此達成分區。

class SortAlgorithmIterable{
    static* partition(columns, left, right) {
        const pivot = columns[right];
        let i = left;
        for (let j = left; j < right; j++) {
            yield false;
            if (columns[j].height < pivot.height) {
                SortAlgorithm.swapColumn(columns[i], columns[j], 30);
                i++;
            }
        }
        SortAlgorithm.swapColumn(columns[i], columns[right], 30);
        return i;
    }
}

透過生成器達成有以下幾個優點:

  • 簡潔性:相比使用 stack 來手動管理子區間的版本,這個方案更加簡潔,使用生成器自動處理遞迴過程,保持程式乾淨。
  • 彈性與可控性:透過 yield 來控制每個步驟的執行,這樣可以非常方便地與動畫系統結合。
  • 可擴展性:這個方案很容易擴展到其他排序演算法,因為它將分區邏輯與主遞迴邏輯分離,易於維護和修改。

結論

雖然手動管理堆疊的方案沒有生成器版本那樣的簡潔,也缺乏經典遞迴的直觀性,但它仍然是一個非常好的練習方式,特別是展示了如何在不依賴遞迴結構的情況下,實現遞迴的效果。這種方法雖然複雜,卻很有趣,因為它逼迫我們重新思考遞迴的核心概念。

結構上也很像在種一個二元樹,即使它又臭又長,我還是很喜歡它。每一步都有明確的處理流程,對於需要詳細控制的場景非常適用。最重要的是,它不會遇到遞迴層數過深而導致堆疊溢出的問題,因此在處理大數據集時更穩定。


上一篇
C4 流動的插入和希爾-迭代生成器驅動的排序動畫
下一篇
C6 合併排序的舞步-視覺化演繹分治法的魅力
系列文
讓演算法起舞:前端特效應用的探索之旅35
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言